BZOJ 2039 employ人员雇佣

Description

作为一个富有经营头脑的富翁,小L决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,(我们用Ei,j表示i经理对j经理的了解程度),即当经理i和经理j同时被雇佣时,经理i会对经理j做出贡献,使得所赚得的利润增加Ei,j。当然,雇佣每一个经理都需要花费一定的金钱Ai,对于一些经理可能他做出的贡献不值得他的花费,那么作为一个聪明的人,小L当然不会雇佣他。 然而,那些没有被雇佣的人会被竞争对手所雇佣,这个时候那些人会对你雇佣的经理的工作造成影响,使得所赚得的利润减少Ei,j(注意:这里的Ei,j与上面的Ei,j 是同一个)。 作为一个效率优先的人,小L想雇佣一些人使得净利润最大。你可以帮助小L解决这个问题吗?

Input

第一行有一个整数N<=1000表示经理的个数 第二行有N个整数Ai表示雇佣每个经理需要花费的金钱 接下来的N行中一行包含N个数,表示Ei,j,即经理i对经理j的了解程度。(输入满足Ei,j=Ej,i)

Output

第一行包含一个整数,即所求出的最大值。

Sample Input

3
3 5 100
0 6 1
6 0 2
1 2 0

Sample Output

1
【数据规模和约定】
20%的数据中N<=10
50%的数据中N<=100
100%的数据中 N<=1000, Ei,j<=maxlongint, Ai<=maxlongint

Solution

看起来各种最小割,先构一个二分图的模型
然而i,j属于不同集合分别有不同代价完全搞不出来
悲伤地看题解发现对于e[i][j]只要S向i,j各连e[i][j],i,j之间连2×e[i][j]
然后每个点向T连a[i]就可以了QAQ
感觉要蠢哭了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>

#define maxn 1000+5
#define maxm 2004000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct sides{
int u,v;ll c;
int next;
}s[maxm];

queue<int> q;
ll ans,f[maxn][maxn];
int first[maxn],cur[maxn],ind;
int n,S,T,h[maxn];

void insert(int u,int v,ll c)
{

s[ind]=(sides){u,v,c,first[u]},first[u]=ind++;
s[ind]=(sides){v,u,0,first[v]},first[v]=ind++;
}

bool bfs()
{

set(h,-1),h[T]=0;
q.push(T);
while( !q.empty() ){
int sd=q.front();q.pop();
for(int i=first[sd];i!=-1;i=s[i].next)
if( s[i^1].c>0 && h[s[i].v]==-1 ){
h[s[i].v]=h[sd]+1;
q.push(s[i].v);
}
}
return h[S]!=-1;
}

ll dfs(int x,ll flow)
{

if( x==T ) return flow;
ll used=0;
for(int &i=cur[x];i!=-1;i=s[i].next)
if( h[s[i].v]+1==h[x] && s[i].c>0 ){
ll w=dfs(s[i].v,min(s[i].c,flow-used));
s[i].c-=w,s[i^1].c+=w,used+=w;
if( used==flow ) return flow;
}
return used;
}

void dinic()
{

while( bfs() ){
for(int i=S;i<=T;i++) cur[i]=first[i];
ans-=dfs(S,LLONG_MAX);
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("2039.in","r",stdin);
freopen("2039.out","w",stdout);
#endif
scanf("%d",&n);
set(first,-1);
S=0,T=n+1;
for(int i=1;i<=n;i++){
int w;
scanf("%d",&w);
insert(i,T,w);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int w;
scanf("%d",&w),ans+=w;
f[i][j]+=w,f[j][i]+=w,f[S][i]+=w;
}
for(int i=S;i<T;i++)
for(int j=S;j<T;j++)
if( f[i][j] ) insert(i,j,f[i][j]);
dinic();
printf("%lld",ans);
return 0;
}